package exams.binary;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class OperationSolution {

    /**
     * 二叉树中和为某一值的路径(一)
     *
     * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
     * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
     * 2.叶子节点是指没有子节点的节点
     * 3.路径只能从父节点到子节点，不能从子节点到父节点
     * 4.总节点数目为n
     *
     * 输入：
     * {5,4,8,1,11,#,9,#,#,2,7},22
     * 返回值：
     * true
     *
     * */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null) {
            return false;
        }

        if(root.left == null && root.right == null && sum - root.val == 0) {
            return true;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }


    /**
     * 二叉搜索树与双向链表
     *
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     * 注意:
     * 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
     * 2.返回链表中的第一个节点的指针
     * 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构
     * 4.你不用输出双向链表，程序会根据你的返回值自动打印输出
     * 输入描述：
     * 二叉树的根节点
     * 返回值描述：
     * 双向链表的其中一个头节点。
     *
     * 输入：
     * {10,6,14,4,8,12,16}
     * 返回值：
     * From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
     * 说明：
     * 输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
     *
     */
    TreeNode head = null;
    TreeNode pre = null;
    public TreeNode convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }

        convert(pRootOfTree.left);
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        convert(pRootOfTree.right);

        return head;
    }


    /**
     * 对称的二叉树
     *
     * 给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
     * */
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return true;
        }
        return isSymmetrical(pRoot.left, pRoot.right);
    }

    public boolean isSymmetrical(TreeNode node1, TreeNode node2) {
        if(node1 == null && node2 == null) {
            return true;
        }
        if(node1 == null || node2 == null || node1.val != node2.val) {
            return false;
        }

        return isSymmetrical(node1.left, node2.right) && isSymmetrical(node1.right, node2.left);
    }


    /**
     * 合并二叉树
     *
     * 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。
     *
     * 输入：
     * {1,3,2,5},{2,1,3,#,4,#,7}
     * 返回值：
     * {3,4,5,5,4,#,7}
     * */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if(t1 == null) {
            return t2;
        }
        if(t2 == null) {
            return t1;
        }

        TreeNode newNode = new TreeNode(t1.val + t2.val);
        newNode.left = mergeTrees(t1.left, t2.left);
        newNode.right = mergeTrees(t1.right, t2.right);

        return newNode;
    }

    /**
     * 二叉树的镜像
     *
     * 操作给定的二叉树，将其变换为源二叉树的镜像
     * 输入：
     * {8,6,10,5,7,9,11}
     * 返回值：
     * {8,10,6,11,9,7,5}
     * */
    public TreeNode mirror (TreeNode pRoot) {
        // write code here
        if(pRoot == null){
            return null;
        }
        TreeNode left = mirror(pRoot.right);
        TreeNode right = mirror(pRoot.left);
        pRoot.left = left;
        pRoot.right = right;

        return pRoot;
    }

    /**
     * 判断是不是二叉搜索树
     *
     * 给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
     *
     * 二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
     * 输入：
     * {1,2,3}
     * 返回值：
     * false
     *
     * 输入：
     * {2,1,3}
     * 返回值：
     * true
     * */
    private int pre1 = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if(root == null) {
            return true;
        }
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val < pre1) {
            return false;
        }
        pre1 = root.val;
        if(!isValidBST(root.right)) {
            return false;
        }

        return true;
    }

    /**
     * 判断是不是完全二叉树
     *
     * 给定一个二叉树，确定他是否是一个完全二叉树。
     *
     * 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
     * */
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if(root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean flag = false;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < queue.size(); i++){
                TreeNode cur = queue.poll();
                if(cur == null) {
                    flag = true;
                } else {
                    if(flag) {
                        return false;
                    }
                    queue.add(cur.left);
                    queue.add(cur.right);
                }
            }
        }

        return true;
    }


    /**
     * 判断是不是平衡二叉树
     *
     * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
     * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
     * 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
     * */
    public boolean isBalancedSolution (TreeNode pRoot) {
        // write code here
        if(pRoot == null) {
            return true;
        }
        int left = deep(pRoot);

        return left != -1;
    }

    private int deep(TreeNode pNode) {
        if(pNode == null) {
            return 0;
        }
        int left = deep(pNode.left);
        if(left == -1) {
            return -1;
        }
        int right = deep(pNode.right);
        if(right == -1) {
            return -1;
        }

        return Math.abs(left - right) > 1? -1 : Math.max(left, right) + 1;
    }

    /**
     * 二叉搜索树的最近公共祖先
     *
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
     * 2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
     * 3.所有节点的值都是唯一的。
     * 4.p、q 为不同节点且均存在于给定的二叉搜索树中。
     * 数据范围:
     * 3<=节点总数<=10000
     * 0<=节点值<=10000
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        List<Integer> pPath = getPath(root, p);
        List<Integer> qPath = getPath(root, q);

        int i = 0;
        int res = -1;
        while(i < pPath.size() && i< qPath.size()) {
            if(pPath.get(i).equals(qPath.get(i))) {
                res = pPath.get(i);
            }
            i++;
        }

        return res;
    }

    private List<Integer> getPath(TreeNode root, int t) {
        List<Integer> res = new ArrayList<>();
        TreeNode node = root;

        while (node.val != t) {
            res.add(node.val);
            if (node.val > t) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        res.add(node.val);

        return res;
    }

//         7
//     1         12
//    0  4      11 14
//      3 5

    /**
     * 在二叉树中找到两个节点的最近公共祖先
     *
     * 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
     *
     * 输入：
     * {3,5,1,6,2,0,8,#,#,7,4},5,1
     * 返回值：
     * 3
     * */
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null) {
            return -1;
        }
        if(root.val == o1 || root.val == o2) {
            return root.val;
        }
        int left = lowestCommonAncestor2(root.left, o1, o2);
        int right = lowestCommonAncestor2(root.right, o1, o2);

        if(left == -1) {
            return right;
        }
        if(right == -1) {
            return left;
        }

        return root.val;
    }


    /**
     * 序列化二叉树
     *
     * 请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
     * 二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）
     * 二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
     *
     *
     *
     * */
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Serialize(root, sb);
        return sb.toString();
    }

    void Serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(",").append("#");
        } else {
            sb.append(",").append(root.val);

            Serialize(root.left, sb);
            Serialize(root.right, sb);
        }
    }

    TreeNode Deserialize(String str) {
        String[] strArr = str.split(",");

        return Deserialize(strArr, new AtomicInteger(1));
    }

    TreeNode Deserialize(String[] strArr, AtomicInteger index) {
        String curStr = strArr[index.getAndIncrement()];
        if("#".equals(curStr)) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(curStr));

        root.left = Deserialize(strArr, index);
        root.right = Deserialize(strArr, index);

        return root;
    }

    /***
     * 重建二叉树
     *
     * 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
     * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
     * 提示:
     * 1.vin.length == pre.length
     * 2.pre 和 vin 均无重复元素
     * 3.vin出现的元素均出现在 pre里
     * 4.只需要返回根结点，系统会自动输出整颗树做答案对比
     *
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        if(preOrder.length == 0 || vinOrder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder[0]);
        for(int i=0; i< vinOrder.length; i++) {
            if(preOrder[0] == vinOrder[i]) {
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1), Arrays.copyOfRange(vinOrder, 0, i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i+1, preOrder.length), Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
            }
        }

        return root;
    }


    /**
     * 输出二叉树的右视图
     *
     * 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
     * 如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树
     *
     * 输入：
     * [1,2,4,5,3],[4,2,5,1,3]
     * 返回值：
     * [1,3,5]
     * */
    public int[] rightView (int[] preOrder, int[] inOrder) {
        // write code here
        TreeNode root = buildTree(preOrder, inOrder);
        ArrayList<Integer> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i =0; i<size; i++) {
                TreeNode cur = queue.poll();
                if(cur.left != null) {
                    queue.add(cur.left);
                }
                if(cur.right != null) {
                    queue.add(cur.right);
                }
                if(i == size - 1) {
                    res.add(cur.val);
                }
            }
        }

        return res.stream().mapToInt(i -> i).toArray();
    }

    private TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if(preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preOrder[0]);
        for(int i=0; i< preOrder.length; i++) {
            if(preOrder[0] == inOrder[i]) {
                root.left = buildTree(Arrays.copyOfRange(preOrder, 1, i + 1), Arrays.copyOfRange(inOrder, 0, i));
                root.right = buildTree(Arrays.copyOfRange(preOrder, i+1, preOrder.length), Arrays.copyOfRange(inOrder, i+1, inOrder.length));
            }
        }

        return root;
    }


    /**
     * 最长无重复子数组
     *
     * 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
     * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
     * */
    public int maxLength (int[] arr) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;

        int p1 = 0;
        for(int p2 =0; p2<arr.length; p2++) {
            int cur = arr[p2];
            if(map.containsKey(cur)) {
                map.put(cur, map.get(cur) + 1);
            } else {
                map.put(cur, 1);
            }
            while(map.get(cur) > 1) {
                map.put(arr[p1], map.get(arr[p1]) - 1);
                p1++;
            }
            res = Math.max(res, p2 - p1 + 1);
        }

        return res;
    }

}
